package org.aplombh.java.awcing.basic.basics.search.binarySearch;

import java.util.function.IntPredicate;

public class MyBinarySearch {

    /**
     * the binarySearch template1
     * Right-partition data satisfy the condition
     *
     * 二分查找模板1
     * 递增数组第一个满足条件的情况
     * check找到不满足条件的位置
     *
     * @param left  left margin 左边界
     * @param right right margin 有边界
     * @return the queried data index 待查询下标
     */
    public static int binarySearchLeftMargin(int[] ints, IntPredicate check, int left, int right) {
        while (left < right) {
            // meddle is the cut-off point index
            // meddle是分界点的下标
            int middle = left + right >> 1;
            // if the middle satisfies the condition, the data to be queried is on the left region
            // 如果middle满足条件，待查询数据在左区域,将区域缩小为[left , middle]
            if (check.test(ints[middle])) right = middle;
                // otherwise, the data to be queried is on the right region
                // 否则带查询数据在右区域，将区域缩小为 [middle + 1, right]
            else left = middle + 1;
        }
        return left;
    }

    /**
     * the binarySearch template2
     * Left-partition data satisfy the condition
     *
     * 二分查找模板2
     * 递增数组最后满足条件的情况
     * check找到不满足条件的位置
     *
     * @param left  left margin 左边界
     * @param right right margin 有边界
     * @return the queried data index 待查询下标
     */
    public static int binarySearchRightMargin(int[] ints, IntPredicate check, int left, int right) {
        while (left < right) {
            // meddle is the cut-off point index
            // meddle是分界点的下标
            int middle = left + right + 1 >> 1;
            // if the middle satisfies the condition, the data to be queried is on the right region
            // 如果middle满足条件，待查询数据在右区域,将区域缩小为[middle , right]
            if (check.test(ints[middle])) left = middle;
                // otherwise, the data to be queried is on the left region
                //否则带查询数据在右区域，将区域缩小为 [middle -1, middle]
            else right = middle - 1;
        }
        return left;
    }
}
